#ifndef BIG_INT_H_
#define BIG_INT_H_

#include <inttypes.h>
#include <type_traits>
#include <string.h>
#include "CuString.h"
#include "CuDebug.h"

template<int>
class SignedInteger;

template <int BITS>
class UnsignedInteger 
{
public:
    static constexpr int N = BITS / 32;
    static_assert(N >= 2);

    struct DivResult
    {
        UnsignedInteger quotient;
        UnsignedInteger remainder;
    };

    __device__ static UnsignedInteger MAX()
    {
        UnsignedInteger max;
        for (size_t i = 0; i < N; ++i)
            max.data[i] = (uint32_t)-1;
        return max;
    }

    __device__ static UnsignedInteger MIN()
    {
        return UnsignedInteger();
    }

    __device__ static UnsignedInteger fromString(const CuString& str)
    {
        UnsignedInteger ret;
        for (int i = 0; i < str.size(); i++)
        {
            ret = ret * 10 + (str[i] - '0');
        }
        return ret;
    }

    __device__ UnsignedInteger()
    {
        memset(data, 0, sizeof(data));
    }

    __device__ explicit UnsignedInteger(uint32_t value[N])
    {
        for (int i = 0; i < N; i++)
            data[i] = value[i];
    }

    __device__ UnsignedInteger(uint64_t value)
        :UnsignedInteger()
    {
        uint32_t *p = (uint32_t*)& value;
        data[0] = p[0];
        data[1] = p[1];
    }

    __device__ UnsignedInteger operator+(const UnsignedInteger& other) const
    {
        UnsignedInteger ret;
        uint64_t carry = 0;
        for (size_t i = 0; i < N; ++i) 
        {
            uint64_t sum = static_cast<uint64_t>(data[i]) + other.data[i] + carry;
            carry = sum >> 32;
            ret.data[i] = static_cast<uint32_t>(sum);
        }
        return ret;
    }

    __device__ UnsignedInteger operator-(const UnsignedInteger& other) const
    {
        UnsignedInteger ret;
        uint64_t borrow = 0;
        for (size_t i = 0; i < N; ++i) {
            uint64_t diff = static_cast<uint64_t>(data[i]) - other.data[i] - borrow;
            if (diff > data[i]) {
                diff += (static_cast<uint64_t>(1) << 32);
                borrow = 1;
            }
            else {
                borrow = 0;
            }
            ret.data[i] = static_cast<uint32_t>(diff);
        }
        return ret;
    }

    __device__ UnsignedInteger operator*(const UnsignedInteger& other) const
    {
        UnsignedInteger<2 * BITS> result;
        for (size_t i = 0; i < N; ++i) {
            uint64_t carry = 0;
            for (size_t j = 0; j < N; ++j) {
                uint64_t prod = static_cast<uint64_t>(data[i]) * other.data[j] + result.data[i + j] + carry;
                carry = prod >> 32;
                result.data[i + j] = static_cast<uint32_t>(prod);
            }
        }
        return (UnsignedInteger)result;
    }

    __device__ UnsignedInteger operator/(const UnsignedInteger& other) const
    {
        return div(other).quotient;
    }

    __device__ UnsignedInteger operator%(const UnsignedInteger& other) const
    {
        return div(other).remainder;
    }

    __device__ bool operator>(const UnsignedInteger& other) const
    {
        return other < *this;
    }

    __device__ bool operator>=(const UnsignedInteger& other) const
    {
        return !(other > *this);
    }

    __device__ bool operator<(const UnsignedInteger& other) const
    {
        for (int i = N - 1; i >= 0; i--)
        {
            if (this->data[i] < other.data[i])
                return true;
            else if (this->data[i] > other.data[i])
                return false;
        }
        return false;
    }

    __device__ bool operator<=(const UnsignedInteger& other) const
    {
        return (other >= *this);
    }

    __device__ bool operator!=(const UnsignedInteger& other) const
    {
        return !(*this == other);
    }

    __device__ bool operator==(const UnsignedInteger& other) const
    {
        for (size_t i = 0; i < N; i++)
        {
            if (data[i] != other.data[i])
                return false;
        }
        return true;
    }

    __device__ explicit operator uint64_t()
    {
        uint64_t *p = (uint64_t*)data;
        return *p;
    }

    template<int M_BITS, std::enable_if_t<(M_BITS > BITS), int> = 0>
    __device__ operator UnsignedInteger<M_BITS>() const
    {
        UnsignedInteger<M_BITS> ret;
        for (int i = 0; i < N; i++)
            ret.data[i] = data[i];

        return ret;
    }

    template<int M_BITS, std::enable_if_t< (M_BITS < BITS), int> = 0 >
    __device__ explicit operator UnsignedInteger<M_BITS>() const
    {
        UnsignedInteger<M_BITS> ret;
        for (int i = 0; i < UnsignedInteger<M_BITS>::N; i++)
            ret.data[i] = data[i];

        return ret;
    }

    template<int M_BITS, std::enable_if_t< (M_BITS <= BITS), int> = 0 >
    __device__ explicit operator SignedInteger<M_BITS>() const;

    template<int M_BITS, std::enable_if_t< (M_BITS > BITS), int> = 0 >
    __device__ operator SignedInteger<M_BITS>() const;

    __device__ CuString toString() const
    {
        UnsignedInteger num = *this;

        UnsignedInteger zero = 0;
        UnsignedInteger ten = 10;

        CuString result;
        while (num != zero) {
            UnsignedInteger remainder = num % ten;
            result = static_cast<char>(remainder.data[0] + '0') + result;
            num = num / ten;
        }
        if (result.isEmpty()) {
            result = "0";
        }
        return result;
    }

    __device__ DivResult div(const UnsignedInteger& divisor) const
    {
        UnsignedInteger<BITS*2> dividend = *this;
        UnsignedInteger quotient;
        UnsignedInteger one = 1;
        while (dividend >= divisor)
        {
            UnsignedInteger<BITS*2> temp = divisor;
            UnsignedInteger multiple = 1;
            while (dividend >= temp + temp)
            {
                temp = temp + temp;
                multiple = multiple + multiple;
            }
            dividend = dividend - temp;
            quotient = quotient + multiple;
        }
        return { quotient,(UnsignedInteger)dividend };
    }

    uint32_t data[N];
};

template <int BITS>
class SignedInteger
{
public:
    static constexpr int N = BITS / 32;
    static_assert(N >= 2);

    __device__ static SignedInteger MAX()
    {
        SignedInteger max;
        for (size_t i = 0; i < N; ++i)
            max.data[i] = (uint32_t)-1;
        max.data[N - 1] &= ~(1 << 31);
        return max;
    }

    __device__ static SignedInteger MIN()
    {
        SignedInteger min;
        min.data[N - 1] |= (1U << 31);
        return min;
    }

    __device__ static SignedInteger fromString(const CuString& str)
    {
        SignedInteger ret;
        bool isNeg = false;
        for (int i = 0; i < str.size(); i++)
        {
            if (i == 0 && str[i] == '-')
            {
                isNeg = true;
                continue;
            }

            ret = ret * 10 + (str[i] - '0');
        }

        if (isNeg)
            return -ret;
        else
            return ret;
    }

    __device__ SignedInteger()
    {
        memset(data, 0, sizeof(data));
    }

    __device__ explicit SignedInteger(uint32_t value[N])
    {
        for (int i = 0; i < N; i++)
            data[i] = value[i];
    }

    __device__ SignedInteger(int32_t value)
        :SignedInteger((int64_t)value)
    {   
    }

    __device__ SignedInteger(uint32_t value)
        :SignedInteger((uint64_t)value)
    {   
    }

    __device__ SignedInteger(int64_t value)
        :SignedInteger()
    {
        uint32_t* p = (uint32_t*)&value;
        data[0] = p[0];
        data[1] = p[1];
        if (value < 0)
        {
            for (int i = 2; i < N; i++)
                data[i] = (uint32_t)-1;
        }
    }

    __device__ SignedInteger(uint64_t value)
        :SignedInteger()
    {
        uint32_t* p = (uint32_t*)&value;
        data[0] = p[0];
        data[1] = p[1];
    }

    // 检查是否为负数
    __device__ bool isNegative() const {
        return (data[N - 1] >> 31) == 1;
    }

    __device__ SignedInteger operator+(const SignedInteger& other) const
    {
        SignedInteger ret;
        uint64_t carry = 0;
        for (size_t i = 0; i < N; ++i)
        {
            uint64_t sum = static_cast<uint64_t>(data[i]) + other.data[i] + carry;
            carry = sum >> 32;
            ret.data[i] = static_cast<uint32_t>(sum);
        }
        return ret;
    }

    __device__ SignedInteger operator-(const SignedInteger& other) const
    {
        SignedInteger ret;
        uint64_t borrow = 0;
        for (size_t i = 0; i < N; ++i) {
            uint64_t diff = static_cast<uint64_t>(data[i]) - other.data[i] - borrow;
            if (diff > data[i]) {
                diff += (static_cast<uint64_t>(1) << 32);
                borrow = 1;
            }
            else {
                borrow = 0;
            }
            ret.data[i] = static_cast<uint32_t>(diff);
        }
        return ret;
    }

    __device__ SignedInteger operator*(const SignedInteger& other) const
    {
        SignedInteger<2 * BITS> result;
        for (size_t i = 0; i < N; i++) {
            uint64_t carry = 0;
            for (size_t j = 0; j < N ; j++) {
                uint64_t prod = static_cast<uint64_t>(data[i]) * other.data[j] + result.data[i + j] + carry;
                carry = prod >> 32;
                result.data[i + j] = static_cast<uint32_t>(prod);
            }
        }
        return (SignedInteger)result;
    }

    __device__ SignedInteger operator/(const SignedInteger& other) const
    {
        return div(other).quotient;
    }

    __device__ SignedInteger operator%(const SignedInteger& other) const
    {
        return div(other).remainder;
    }

    __device__ SignedInteger operator-() const
    {
        UnsignedInteger<BITS> max = UnsignedInteger<BITS>::MAX();
        UnsignedInteger<BITS> neg;
        neg = max - (UnsignedInteger<BITS>)(*this) + 1;
        return (SignedInteger)neg;
    }

    __device__ bool operator>(const SignedInteger& other) const
    {
        return other < *this;
    }

    __device__ bool operator>=(const SignedInteger& other) const
    {
        return !(other > *this);
    }

    __device__ bool operator<(const SignedInteger& other) const
    {
        bool thisNegative = isNegative();
        bool otherNegative = other.isNegative();
        if (thisNegative != otherNegative) {
            return thisNegative;
        }
        if (thisNegative) {
            // 都是负数，绝对值大的反而小
            for (int i = 0; i < N; ++i) {
                if (data[i] > other.data[i]) {
                    return false;
                }
                else if (data[i] < other.data[i]) {
                    return true;
                }
            }
            return false;
        }
        else {
            // 都是正数，正常比较
            for (int i = 0; i < N; ++i) {
                if (data[i] > other.data[i]) {
                    return false;
                }
                else if (data[i] < other.data[i]) {
                    return true;
                }
            }
            return false;
        }
    }

    __device__ bool operator<=(const SignedInteger& other) const
    {
        return (other >= *this);
    }

    __device__ bool operator!=(const SignedInteger& other) const
    {
        return !(*this == other);
    }

    __device__ bool operator==(const SignedInteger& other) const
    {
        for (size_t i = 0; i < N; i++)
        {
            if (data[i] != other.data[i])
                return false;
        }
        return true;
    }

    __device__ explicit operator int64_t()
    {
        int64_t *p = (int64_t*)data;
        return *p;
    }

    template<int M_BITS, std::enable_if_t<(M_BITS > BITS), int> = 0>
    __device__ operator SignedInteger<M_BITS>() const
    {
        SignedInteger<M_BITS> ret;
        for (int i = 0; i < N; i++)
            ret.data[i] = data[i];
        if (*this < 0)
        {
            for (int i = N; i < SignedInteger<M_BITS>::N; i++)
                ret.data[i] = (uint32_t)-1;
        }
        return ret;
    }

    template<int M_BITS, std::enable_if_t< (M_BITS < BITS), int> = 0 >
    __device__ explicit operator SignedInteger<M_BITS>() const
    {
        SignedInteger<M_BITS> ret;
        for (int i = 0; i < SignedInteger<M_BITS>::N; i++)
            ret.data[i] = data[i];
        return ret;
    }

    template<int M_BITS>
    __device__ explicit operator UnsignedInteger<M_BITS>() const
    {
        UnsignedInteger<M_BITS> ret;
        if (M_BITS >= BITS)
        {
            for (int i = 0; i < N; i++)
                ret.data[i] = data[i];
        }
        else
        {
            for (int i = 0; i < UnsignedInteger<M_BITS>::N; i++)
                ret.data[i] = data[i];
        }
        return ret;
    }

    __device__ CuString toString() const
    {
        UnsignedInteger<BITS> num; 
        bool neg = this->isNegative();
        if (neg)
        {
            num = (UnsignedInteger<BITS>)(-(*this));
        }
        else
        {
            num = (UnsignedInteger<BITS>)(*this);
        }

        CuString result = num.toString();
        if (neg)
            result = "-" + result;
        return result;
    }

    uint32_t data[N];

protected:
    struct DivResult
    {
        SignedInteger quotient;
        SignedInteger remainder;
    };

    __device__ DivResult div(const SignedInteger& divisor) const
    {
        UnsignedInteger<BITS> max = UnsignedInteger<BITS>::MAX();
        UnsignedInteger<BITS> self;
        UnsignedInteger<BITS> other; 
        bool self_neg = isNegative();
        bool other_neg = divisor.isNegative();
        if (!self_neg)
            self = (UnsignedInteger<BITS>)(*this);
        else
            self = (UnsignedInteger<BITS>)(-(*this));
        
        if (!other_neg)
            other = (UnsignedInteger<BITS>)divisor;
        else
            other = (UnsignedInteger<BITS>)(-divisor);

        auto un_ret = self.div(other);
        SignedInteger quotient, remainder;
        if (self_neg != other_neg)
            quotient = -(SignedInteger)un_ret.quotient;
        else
            quotient = (SignedInteger)un_ret.quotient;

        if(self_neg)
            remainder = -(SignedInteger)un_ret.remainder;
        else
            remainder = (SignedInteger)un_ret.remainder;

        return { quotient,remainder };
    }
};

template<int BITS>
template<int M_BITS, std::enable_if_t<(M_BITS <= BITS), int> >
__device__ UnsignedInteger<BITS>::operator SignedInteger<M_BITS>() const
{
    SignedInteger<M_BITS> ret;
    for (int i = 0; i < SignedInteger<M_BITS>::N; i++)
        ret.data[i] = data[i];
    return ret;
}

template<int BITS>
template<int M_BITS, std::enable_if_t<(M_BITS > BITS), int> >
__device__ UnsignedInteger<BITS>::operator SignedInteger<M_BITS>() const
{
    SignedInteger<M_BITS> ret;
    for (int i = 0; i < N; i++)
        ret.data[i] = data[i];
    return ret;
}

typedef UnsignedInteger<128> uint128_t;
typedef UnsignedInteger<256> uint256_t;
typedef UnsignedInteger<512> uint512_t;

typedef SignedInteger<128> int128_t;
typedef SignedInteger<256> int256_t;
typedef SignedInteger<512> int512_t;

template <int BITS>
__device__ CuDebug operator<<(CuDebug dbg, const SignedInteger<BITS> &num)
{
    dbg << num.toString();
    return dbg;
}

template <int BITS>
__device__ CuDebug operator<<(CuDebug dbg, const UnsignedInteger<BITS> &num)
{
    dbg << num.toString();
    return dbg;
}

#endif